Apple Developer Connection 1998 Fall: Game Toolkit/Disc.iso/SDKs/PCI Driver Development Kit/• Tools/Utility/LogLibrary 950622/Src/MathLib64.c

C/C++ Source or Header | 1996-08-20 | 5.6 KB | 188 lines | [TEXT/MPCC]

/*                                        MathLib64.c                                    */
/*
 * Add64.c
 * Copyright © 1995 Apple Computer Inc. All Rights Reserved.
 *
 *        Add64(&aWideValue, &bWideValue, &result)        result = a + b
 *        Subtract64(&aWideValue, &bWideValue, &result)    result = a - b
 *        Multiply64(&aWideValue, &longValue, &result)    result = a * b
 *        Divide64(&aWideValue, &bWideValue, &result)        result = a / b;
 *                                                        a = a mod b (remainder)
 *
 * The multiply and divide routines were adapted from "A Guide to Illiac Programming"
 * Written by
 *    Martin Minow
 */
#include <Types.h>

/*
 * Copy these prototypes to your calling application header file.
 */
void                        Add64(
        register const UnsignedWide    *aPtr,
        register const UnsignedWide    *bPtr,
        register UnsignedWide        *result
    );
void                        Subtract64(
        register const UnsignedWide    *aPtr,
        register const UnsignedWide    *bPtr,
        register UnsignedWide        *result
    );
void                        Multiply64(
        const UnsignedWide        *multiplicand,    /* Multiplier * multiplicand        */
        UInt32                    multiplier,        /* yields result                    */
        UnsignedWide            *resultPtr
    );
void                        Divide64(            /* quotient = dividend / divisor    */
        UnsignedWide            *dividendPtr,    /* Dividend, becomes remainder        */
        const UnsignedWide        *divisorPtr,    /* Divisor, unchanged                */
        UnsignedWide            *quotientPtr    /* Quotient, result                    */
    );


static const UInt32        kHighBit = 0x80000000L;

/*
 * 64-bit addition. Although the parameters are defined as UnsignedWide, they
 * should work correctly for signed wide.
 */
void
Add64(
        register const UnsignedWide    *aPtr,
        register const UnsignedWide    *bPtr,
        register UnsignedWide        *result
    )
{
        result->lo = aPtr->lo + bPtr->lo;
        result->hi = aPtr->hi + bPtr->hi;
        /*
         * Carry from low-word to high-word if the unsigned result->lo is
         * less than the unsigned interpretation of either source value.
         */
        if (((UInt32) result->lo) < ((UInt32) aPtr->lo))
            result->hi++;
}

/*
 * Subtract (2nd argument) from (1st argument):
 */
void
Subtract64(
        register const UnsignedWide    *aPtr,
        register const UnsignedWide    *bPtr,
        register UnsignedWide        *result
    )
{
        if (aPtr->lo >= bPtr->lo)
            result->hi = aPtr->hi - bPtr->hi;
        else {
            result->hi = (aPtr->hi - 1) - bPtr->hi;
        }
        result->lo = aPtr->lo - bPtr->lo;
}

/*
 * This is a bit-by-bit (i.e., inefficient) multiplication routine that multiplies
 * two unsigned numbers, returning a 64-bit result.
 *
 * Adapted from "A Guide to Illiac Programming" 1961 Edition.
 */
void
Multiply64(
        const UnsignedWide        *multiplicand,    /* Multiplier * multiplicand        */
        UInt32                    multiplier,        /* yields result                    */
        UnsignedWide            *resultPtr
    )
{
        register int            i;
        UnsignedWide            accumulator;    /* accumulator and resultLo form    */
        register UInt32            resultLo;        /* a 96-bit intermediate register    */

        resultLo = 0;                            /* Clear the result accumulator        */
        accumulator.hi = accumulator.lo  = 0;    /* Clear more of the result            */
        for (i = 0; i < 32; i++) {
            if ((multiplier & 1) != 0)
                Add64(multiplicand, &accumulator, &accumulator);
            multiplier >>= 1;                    /* Right shift multiplier            */
            resultLo >>= 1;                        /* 64-bit right shift of result        */
            if ((accumulator.lo & 1) != 0)        /* Carry from mid word?                */
                resultLo |= kHighBit;            /* Yes, carry into the low word.    */
            accumulator.lo >>= 1;                /* Right-shift mid word                */
            if ((accumulator.hi & 1) != 0)        /* Carry from high to mid?            */
                accumulator.lo |= kHighBit;        /* Yes.                                */
            accumulator.hi >>= 1;                /* Finish the 64-bit shift            */
        }
        resultPtr->hi = accumulator.lo;
        resultPtr->lo = resultLo;
}

/*
 * This is a bit-by-bit (i.e., inefficient) division routine that will handle a
 * 64-bit unsigned divide. The computation results in:
 *         quotient = dividend / divisor, dividend := remainder.
 * Although it looks pretty ugly in C, Risk pipeline optimization should make short
 * work of the algorithm.
 *
 * Adapted from "A Guide to Illiac Programming" 1961 Edition.
 */
void
Divide64(
        UnsignedWide            *dividendPtr,    /* Dividend, becomes remainder        */
        const UnsignedWide        *divisorPtr,    /* Divisor, unchanged                */
        UnsignedWide            *quotientPtr    /* Quotient, result                    */
    )
{
        register int            i;
        UnsignedWide            accumulator[2];

        /*
         * Store the dividend in the low-word of a 128 bit accumulator
         */
        accumulator[0].hi = accumulator[0].lo = 0;
        accumulator[1] = *dividendPtr;
        quotientPtr->hi = quotientPtr->lo = 0;
        for (i = 0; i < 64; i++) {
            /*
             * Left-shift the 64-bit quotient to make room for a new bit.
             */
            quotientPtr->hi <<= 1;
            if ((quotientPtr->lo & kHighBit) != 0)
                quotientPtr->hi |= 1;
            quotientPtr->lo <<= 1;
            /*
             * Left-shift the 128-bit accumulator. The divisor shifts into
             * the high 64 bit word.
             */
            accumulator[0].hi <<= 1;
            if ((accumulator[0].lo & kHighBit) != 0)
                accumulator[0].hi |= 1;
            accumulator[0].lo <<= 1;
            if ((accumulator[1].hi & kHighBit) != 0)
                accumulator[0].lo |= 1;
            accumulator[1].hi <<= 1;
            if ((accumulator[1].lo & kHighBit) != 0)
                accumulator[1].hi |= 1;
            accumulator[1].lo <<= 1;
            /*
             * Compare the high-word of the accumulator to the divisor.
             */
            if (accumulator[0].hi > divisorPtr->hi
             || (accumulator[0].hi == divisorPtr->hi
              && accumulator[0].lo >= divisorPtr->lo)) {
                /*
                 * Accumulator is >= divisor, put a bit into the quotient
                 * (remember, we left-shifted it first) and subtract the
                 * divisor from the accumulator high word
                 */
                quotientPtr->lo |= 1;
                if (accumulator[0].lo >= divisorPtr->lo)
                    accumulator[0].hi -= divisorPtr->hi;
                else {
                    accumulator[0].hi -= (divisorPtr->hi + 1);
                }
                accumulator[0].lo -= divisorPtr->lo;
            }
        }
        *dividendPtr = accumulator[0];
}